| |
| description |
27 pages
|
|
Die schnellsten Algorithmen zur Mustersuche in Texten sind Varianten
des genialen Algorithmus BoMo von Boyer und Moore. Wenn Text und
Muster nicht zusammenpassen, verwendet BoMo Tabellen, um die
größten zulässigen Verschiebungen zu ermitteln. Eine effiziente
Berechnung dieser Tabellen wurde von Knuth angegeben.
Hier wird sowohl auf die den Algorithmen KMP von Knuth, Morris und
Pratt, BoMo und ESS zugrundeliegenden Ideen eingegangen, als auch
die Implementierung ihrer Verschiebetabellen detailliert
beschrieben.
The fastest known algorithms for pattern matching in strings are
derivatives of the ingenious algorithm BoMo of Boyer and Moore. On
mismatch tables are used by BoMo to ascertain the largest possible
pattern shifts. An efficient scheme of computing these tables was
given by Knuth.
In this report we recapitulate the key ideas underlying the
algorithms KMP of Knuth, Morris and Pratt, BoMo, and ESS, as well as
presenting the implementation of their shift tables in detail.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Technical Report
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-1995-01/TR-1995-01.pdf
|
| contributor |
Betriebssoftware (IFI)
|
| format |
application/pdf
|
| subject |
Nonnumerical Algorithms and Problems (CR F.2.2)
|
| Information Search and Retrieval (CR H.3.3)
|
| Wortsuche
|
| Mustererkennung
|
| Boyer-Moore
|
| relation |
Technical Report No. 1995/01
|